class Solution:
    def numSquares(self, n: int) -> int:
        # 初始化 dp 数组，dp[i] 表示组成 i 的最少平方数数量
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        # 预计算所有可能的平方数
        squares = [i * i for i in range(1, int(n ** 0.5) + 1)]

        # 动态规划填表
        for i in range(1, n + 1):
            for sq in squares:
                if sq > i:
                    break
                dp[i] = min(dp[i], dp[i - sq] + 1)

        return dp[n]

if __name__ == "__main__":
    solution = Solution()
    n = int(input("请输入一个正整数 n："))
    result = solution.numSquares(n)
    print(f"组成 {n} 的最少完全平方数数量为：{result}")